package data;

import java.util.*;

public class LRUCache {

    int capacity;
    HashMap<Integer , DequeNode> cache;
    DequeNode head;
    DequeNode tail;

    static class DequeNode {
        int val;
        int key;
        DequeNode next;
        DequeNode pre;
        DequeNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public LRUCache(int capacity) {
        this.cache = new HashMap<>(capacity);
        this.capacity =capacity;
    }

    public int get(int key) {
        DequeNode node = this.cache.get(key);
        if(node == null) {
            return -1;
        }
        moveToHead(node);
        return head.val;
    }

    public void put(int key, int value) {
        DequeNode node = this.cache.get(key);
        if(node == null) {
            node = new DequeNode(key,value);
            if(cache.size() >= capacity) {
                deleteTail();
            }
        } else {
            node.val = value;
        }
        this.cache.put(key,node);
        moveToHead(node);

    }

    public void moveToHead(DequeNode node) {
        if(head == null) {
            head = node;
            tail = node;
        } else if(head != node){
            if(node == tail) {
                tail = node.pre;
                tail.next = null;
            }
            if(node.pre != null) {
                node.pre.next = node.next;
                if(node.next != null) {
                    node.next.pre = node.pre;
                }
            }
            node.pre = null;
            node.next = head;
            head.pre = node;
            head = node;
        }
    }

    public void deleteTail() {
        if(tail == null) {
            return;
        }
        this.cache.remove(tail.key);

        if(tail.pre != null) {
            this.tail.pre.next = null;
        }

        this.tail = tail.pre;
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(3);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        lruCache.put(4,4);

        System.out.println(lruCache.get(4));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(2));
        System.out.println(lruCache.get(1));

        lruCache.put(5,5);

        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(2));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
        System.out.println(lruCache.get(5));
    }
}
